|
In geometry, a polygon ''P'' in the plane is called monotone with respect to a straight line ''L'', if every line orthogonal to ''L'' intersects ''P'' at most twice. Similarly, a polygonal chain ''C'' is called monotone with respect to a straight line ''L'', if every line orthogonal to ''L'' intersects ''C'' at most once. For many practical purposes this definition may be extended to allow cases when some edges of ''P'' are orthogonal to ''L'', and a simple polygon may be called monotone if a line segment that connects two points in ''P'' and is orthogonal to ''L'' completely belongs to ''P''. Following the terminology for monotone functions, the former definition describes polygons strictly monotone with respect to ''L''. The "with respect to" part is necessary for drawing the strict/nonstrict distinction: a polygon nonstrictly monotone with respect to ''L'' is strictly monotone with respect to a line ''L1'' rotated from ''L'' by a sufficiently small angle. ==Properties== Assume that ''L'' coincides with the ''x''-axis. Then the leftmost and rightmost vertices of a monotone polygon decompose its boundary into two monotone polygonal chains such that when the vertices of any chain are being traversed in their natural order, their X-coordinates are monotonically increasing or decreasing. In fact, this property may be taken for the definition of monotone polygon and it gives the polygon its name. A convex polygon is monotone with respect to any straight line and a polygon which is monotone with respect to any straight line is convex. A linear time algorithm is known to report all directions in which a given simple polygon is monotone.〔.〕 It was generalized to report all ways to decompose a simple polygon into two monotone chains (possibly monotone in different directions.)〔.〕 Point in polygon queries with respect to a monotone polygon may be answered in logarithmic time after linear time preprocessing (to find the leftmost and rightmost vertices).〔 A monotone polygon may be easily triangulated in linear time. For a given set of points in the plane, a bitonic tour is a monotone polygon that connects the points. The minimum perimeter bitonic tour for a given point set with respect to a fixed direction may be found in polynomial time using dynamic programming.〔''Introduction to Algorithms'', 2nd ed., T. H. Cormen, C. E. Leiserson, R. Rivest, and C. Stein, MIT Press, 2001. Problem 15-1, p. 364.〕 It is easily shown that such a minimal bitonic tour is a simple polygon: a pair of crossing edges may be replaced with a shorter non-crossing pair while preserving the bitonicity of the new tour. A simple polygon may be easily cut into monotone polygons in ''O''(''n'' log ''n'') time. However, since a triangle is a monotone polygon, polygon triangulation is in fact cutting a polygon into monotone ones, and it may be performed for simple polygons in ''O''(''n'') time. Cutting a simple polygon into the minimal number of uniformly monotone polygons (i.e., monotone with respect to the same line) can be performed in polynomial time.〔.〕 In the context of motion planning, two nonintersecting monotone polygons are separable by a single translation (i.e., there exists a translation of one polygon such that the two become separated by a straight line into different halfplanes) and this separation may be found in linear time.〔.〕 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Monotone polygon」の詳細全文を読む スポンサード リンク
|